home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Oh!X 2001 Spring
/
Oh!X 2001 Spring Special CD-ROM (Japan).7z
/
Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin
/
PUZZLE
/
Puz02
/
hex1.c
next >
Wrap
C/C++ Source or Header
|
2000-06-28
|
2KB
|
124 lines
/*
* hex1.c : パズル「ヘックス」 15 パズルの変形バージョン
*
*/
/*
1------2
/ \ / \
3------4------5
\ / \ /
6------0
座標
0------1
/ \ / \
2------3------4
\ / \ /
5------6
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 7
/* 最大の状態数 7! = 5040 */
#define MAX_STATE 5040
/* 隣接リスト */
const char adjacent[SIZE][7] = {
1, 2, 3, -1, -1, -1, -1, /* 0 */
0, 3, 4, -1, -1, -1, -1, /* 1 */
0, 3, 5, -1, -1, -1, -1, /* 2 */
0, 1, 2, 4, 5, 6, -1, /* 3 */
1, 3, 6, -1, -1, -1, -1, /* 4 */
2, 3, 6, -1, -1, -1, -1, /* 5 */
3, 4, 5, -1, -1, -1, -1 /* 6 */
};
/* キュー */
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_postion[MAX_STATE];
short prev_state[MAX_STATE];
int count = 0;
/* 初期状態 */
char init_state[SIZE] = {
1, 5, 2, 6, 3, 4, 0
};
/* 最終状態 */
char final_state[SIZE] = {
1, 2, 3, 4, 5, 6, 0
};
/* 同じ状態があるか */
int check_same_state( int n )
{
int i;
for( i = 0; i < n; i++ ){
count++;
if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
}
return FALSE;
}
/* 結果を出力 */
void print_answer( int n )
{
int i;
if( n != 0 ) print_answer( prev_state[n] );
for( i = 0; i < SIZE; i++ ){
printf("%d ", state[n][i] );
}
printf("\n");
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1, i;
/* 初期化 */
memcpy( state[0], init_state, SIZE );
space_postion[0] = 6;
prev_state[0] = -1;
while( front < rear ){
int s = space_postion[front];
int n;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 状態をコピー */
memcpy( state[rear], state[front], SIZE );
/* 移動 */
state[rear][s] = state[rear][n];
state[rear][n] = 0;
space_postion[rear] = n;
prev_state[rear] = front;
if( !memcmp( state[rear], final_state, SIZE ) ){
print_answer( rear );
printf("状態数 %d 個\n", rear );
return;
} else if( !check_same_state( rear ) ){
/* 登録 */
rear++;
}
}
front++;
}
}
int main()
{
int start, end;
start = clock();
search();
end = clock();
printf("比較回数 %d, 時間 %d \n", count, end - start );
return 0;
}
/* end of file */